#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "table.h"

#define TableSize 4096

typedef struct bucket bucket;

struct bucket {
	void *key;	// to resolve the hash conflict
	void *value;
	bucket *next; // to form the linked list
};

struct table {
	bucket* buckets[TableSize];
};

table* T_empty() {
	table* tab = (table*)malloc(sizeof(*tab));
	memset(tab->buckets, 0, sizeof(tab->buckets));
	return tab;
}

int hash(void* key) {
	int hashIndex = (unsigned long long)key % TableSize;
	return hashIndex;
}

static bucket* T_findBucket(table* tab, void* key) {
	// return the pointer to the bucket with specified 'key'
	// if 'key' does not occur in the 'tab', then return NULL
	int hashIndex = hash(key);
	for(bucket *p = tab->buckets[hashIndex]; p; p = p->next) {
		if(p->key == key)
			return p;
	}
	return NULL;
}

int T_count(table* tab, void* key) {
	return T_findBucket(tab, key) != NULL;
}

void* T_look(table* tab, void* key) {
	// return the value mapped from 'key'
	// if 'key' does not occur in the 'tab', then return NULL
	bucket* p = T_findBucket(tab, key);
	if(p)
		return p->value;
	else
		return NULL;
}


void T_insert(table* tab, void* key, void* value) {
	bucket* p = T_findBucket(tab, key);
	if(p) 
		p->value = value;
	else {
		int hashIndex = hash(key);
		bucket* b = (bucket*)malloc(sizeof(*b));
		b->key = key;
		b->value = value;
		b->next = tab->buckets[hashIndex];		
		tab->buckets[hashIndex] = b;
	}
}

void T_remove(table* tab, void* key) {
	int hashIndex = hash(key);
	bucket** pp = &(tab->buckets[hashIndex]); // pointer to pointer
	bucket* p;
	while(p = *pp) {
		if(p->key != key)
			pp = &(p->next);
		else {
			*pp = p->next;
			free(p);
			break;
		}
	}
}

static void T_free(bucket* b) {
	if(!b)
		return;
	T_free(b->next);
	free(b);
}

void T_clear(table* tab) {
	for(int i = 0; i < TableSize; ++i) 
		T_free(tab->buckets[i]);
	free(tab);
}

void T_dump(table* tab, void (*func)(void *value)) {
	for(int i = 0; i < TableSize; ++i) {
		for(bucket *p = tab->buckets[i]; p; p = p->next)
			func(p->value);
	}
}

